/*
 * @lc app=leetcode.cn id=738 lang=java
 *
 * [738] 单调递增的数字
 */

// @lc code=start
class Solution {
    //怎么都是贪心，真就贪心月吗？N在int的范围内
    /*
     从后往前，如果这一位数字大于后面一位数字，直接将此数字减1，后面所有数字置为9
     因为反正第一位数字减了一。
    */
    // 用char[]数组实现，效率高一些
    public int monotoneIncreasingDigits(int N) {
        if(N<10){
            return N;
        }

        char[] num = Integer.toString(N).toCharArray();
        int f = num.length-1;//标志位，记录哪一位减了一
        for(int i=num.length-2 ;i>=0;i--){
            //关键是1000这种情况要怎么处理。
            if(num[i]>num[i+1]){//大于后面的数字
                f = i;
                num[i]--;
            }
        }
        for(int i = num.length-1; i>f; i--){
            num[i]='9';
        }
        return Integer.parseInt(new String(num));//这里用num.toString()是不行的，返回的是hashcode
    }

    //用StringBuilder实现，效率较低，这是第一次的想法
    public int monotoneIncreasingDigits1(int N) {
        if(N<10){
            return N;
        }
        StringBuilder S =new StringBuilder(Integer.toString(N));
        S.reverse();//反过来好操作一点
        int f = 0;//标志位，记录哪一位减了一
        for(int i=1 ;i<S.length();i++){
            //关键是1000这种情况要怎么处理。
            if(S.charAt(i)>S.charAt(i-1)){//大于前一个
                f = i;
                char t = S.charAt(i);
                S.setCharAt(i, (char) (t - 1));
            }
        }
        for(int i =0;i<f;i++){
            S.setCharAt(i, '9');
        }
        return Integer.parseInt(S.reverse().toString());
        
    }
}
// @lc code=end

